package 题目集.动态规划.背包问题;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 某公司游戏平台的夏季特惠开始了，你决定入手一些游戏 现在你一共有X元的预算，平台上所有的 n 个游戏均有折扣 标号为 i
 * 的游戏的原价a_i元，现价只要b_i元 也就是说该游戏可以优惠 a_i - b_i，并且你购买该游戏能获得快乐值为w_i
 * 由于优惠的存在，你可能做出一些冲动消费导致最终买游戏的总费用超过预算 只要满足 : 获得的总优惠金额>=超过预算的总金额 那在心理上就不会觉得吃亏
 * 现在你希望在心理上不觉得吃亏的前提下，获得尽可能多的快乐值。 测试链接 : https://leetcode.cn/problems/tJau2o/
 * 最终快乐值为：w1+w2+..wk 花费=a-b-b。(a-b是优惠的金额)
 *
 * 这一题不能直接用裸的dp，因为价钱的范围太大了。 需要先对每个物品的实际价值处理下
 */
public class ch02_夏季特惠2 {
	static int[] w;
	static long[] c;
	static long[][] dp;
	static int n, sum, m; // m:实际需要考虑的个数
	static long ans = 0;
	static PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

	public static void main(String[] args) {
		Reader2 sc = new Reader2(System.in);
		n = sc.nextInt();
		sum = sc.nextInt();
		w = new int[n+1];
		c = new long[n+1];
		for (int i = 1; i <= n; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int v = sc.nextInt();
			int wi = a - b - b;
			if (wi >= 0) {
				ans += v;
				sum+=wi;
			} else {
				m++;
				w[m] = -wi;
				c[m] = v;
			}
		}
		ans+=dp();
		pw.println(ans);
		pw.flush();
	}

	public static long dp() {
		dp = new long[m + 1][sum + 1];
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= sum; j++) {
				long chose=0,nochose=dp[i-1][j];
				if(j>=w[i]) {
					chose=dp[i-1][j-w[i]]+c[i];
				}
				dp[i][j]=Math.max(chose,nochose);
			}
		}
		return dp[m][sum];
	}

	static class Reader2 {
        static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public Reader2(Object... o) {
        }

        public int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {}
            return (int) in.nval;
        }
}
}
